package com.zjj.algorithm.learning.atguigu.tree.avl;


/**
 * 平衡二叉树测试
 *
 * @author zjj_admin
 * @date 2022/12/3 17:48
 */
public class AvlTreeDemo {

    public static void main(String[] args) {
//        int[] arr = new int[]{4, 3, 6, 5, 7, 8};
//        int[] arr = new int[]{10, 12, 8, 9, 7, 6};
        int[] arr = new int[]{10, 11, 7, 6, 8, 9};
        AvlTree avlTree = new AvlTree();
        for (int i = 0; i < arr.length; i++) {
            avlTree.addNode(new AvlNode(arr[i]));
        }

        avlTree.midOrder();
        int height = avlTree.getRoot().height();
        int leftHeight = avlTree.getRoot().leftHeight();
        int rightHeight = avlTree.getRoot().rightHeight();
        System.out.println();
        System.out.println("height = " + height + " 左子树高度：" + leftHeight + " 右子树高度：" + rightHeight);
    }
}


class AvlTree {
    /**
     * 二叉排序树的根节点
     */
    private AvlNode root;

    public AvlNode getRoot() {
        return root;
    }

    public void addNode(AvlNode node) {
        if (this.root == null) {
            this.root = node;
        } else {
            this.root.add(node);
        }
    }

    public AvlNode searchNode(int val) {
        if (this.root == null) {
            return null;
        } else {
            return this.root.searchNode(val);
        }
    }


    public AvlNode searchParentNode(int val) {
        if (this.root == null) {
            return null;
        } else {
            if (this.root.no == val) {
                return null;
            }
            return this.root.searchParentNode(val);
        }
    }


    /**
     * 删除二叉排序树的节点
     * 1、删除叶子结点
     * 通过目标节点（target）的父节点，通过父节点直接删除
     * 2、删除只有一颗子树的节点
     * 将父节点指向目标节点的指针指向目标节点的子节点即可
     * 3、删除有两颗子树的节点
     * 3.1：可以选择从左子树中寻找最大的节点替换目标节点
     * 3.2：可以选择从右子树中寻找最小的节点替换目标节点
     *
     * @param val 目标节点
     */
    public void del(int val) {
        if (this.root == null) {
            return;
        }
        //获取目标节点
        AvlNode targetNode = searchNode(val);
        //当没有找到目标节点时，直接返回
        if (targetNode == null) {
            return;
        }
        //获取父节点
        AvlNode parentNode = searchParentNode(val);
        if (parentNode == null) {
            //根节点没有子节点时，说明根节点就是目标节点，删除根节点即可
            if (root.left == null && root.right == null) {
                this.root = null;
            }
            if (root.right != null && root.left == null) {
                root = root.right;

            }
            if (root.left != null && root.right == null) {
                root = root.left;
            }
            if (root.left != null && root.right != null) {
                AvlNode minNode = this.root.right.getMinNode();
                AvlNode temp = new AvlNode(minNode.no);
                //将原始的最小的节点删除
                del(minNode.no);
                //让临时节点成为根节点
                this.root = temp;
                temp.left = targetNode.left;
                temp.right = targetNode.right;
                //最后将右侧的最小的节点删除

            }
        } else {
            //当目标节点是叶子节点是
            if (targetNode.left == null && targetNode.right == null) {
                if (parentNode.left == targetNode) {
                    parentNode.left = null;
                } else {
                    parentNode.right = null;
                }
                return;
            }
            //当目标节点只存在一个子节点时
            //当父节点的左节点是目标节点，并且目标节点的右子节点为 null 时
            if (targetNode.right == null) {
                if (parentNode.left == targetNode) {
                    parentNode.left = targetNode.left;
                } else {
                    parentNode.right = targetNode.left;
                }
                return;
            }
            if (targetNode.left == null) {
                if (parentNode.left == targetNode) {
                    parentNode.left = targetNode.right;
                } else {
                    parentNode.right = targetNode.right;
                }
                return;
            }

            //当目标节点存在两个子节点时
            //获取右子树中的最小的节点
            AvlNode rightMinNode = targetNode.right.getMinNode();
            AvlNode temp = new AvlNode(rightMinNode.no);
            del(rightMinNode.no);
            if (parentNode.left == targetNode) {
                parentNode.left = temp;
                temp.left = targetNode.left;
                temp.right = targetNode.right;
            }
            if (parentNode.right == targetNode) {
                parentNode.right = temp;
                temp.left = targetNode.left;
                temp.right = targetNode.right;
            }

        }


    }


    public void midOrder() {
        if (this.root == null) {
            System.out.println("二叉排序树没有节点，不能中序遍历");
        } else {
            this.root.midOrder();
        }
    }
}

/**
 * 二叉排序树的节点
 */
class AvlNode {
    int no;
    AvlNode left;
    AvlNode right;

    public AvlNode(int no) {
        this.no = no;
    }


    /**
     * 获取以当前节点为根节点的树的高度
     *
     * @return
     */
    public int height() {
        int lh = this.left == null ? 0 : this.left.height();
        int rh = this.right == null ? 0 : this.right.height();
        return Math.max(lh, rh) + 1;
    }

    /**
     * 获取左子树的高度
     *
     * @return
     */
    public int leftHeight() {
        if (this.left == null) {
            return 0;
        } else {
            return this.left.height();
        }
    }


    /**
     * 获取右子树的高度
     *
     * @return
     */
    public int rightHeight() {
        if (this.right == null) {
            return 0;
        } else {
            return this.right.height();
        }
    }


    /**
     * 左旋转的方法
     */
    public void leftRoute() {
        //1、创建一个和当前节点右子节点值相同的新节点
        AvlNode newNode = new AvlNode(this.no);
        //2、将新节点的左子节点指向当前节点的左子节点
        newNode.left = this.left;
        //3、将新节点的右子节点指向当前节点的右子节点的左子节点
        newNode.right = this.right.left;
        //修改当前节点的值
        this.no = this.right.no;
        this.right = this.right.right;
        //将当前节点的左子树指向新节点
        this.left = newNode;

    }


    /**
     * 向右旋转
     */
    public void rightRoute() {
        AvlNode newNode = new AvlNode(this.no);
        newNode.right = this.right;
        //新节点的左节点指向当前节点的左节点的右子节点
        newNode.left = this.left.right;
        this.no = this.left.no;
        this.left = this.left.left;
        this.right = newNode;

    }

    /**
     * 添加节点，需要满足二叉排序树的要求
     *
     * @param node
     */
    public void add(AvlNode node) {
        if (node == null) {
            return;
        }
        //当当前节点大于 node 时，就将 node 添加到当前节点的左子节点上
        if (this.no > node.no) {
            if (this.left == null) {
                this.left = node;
            } else {
                //当左子节点不为null时，就递归遍历添加到左子节点
                this.left.add(node);
            }
        } else {
            if (this.right == null) {
                this.right = node;
            } else {
                //当右子节点不为null时，就递归遍历添加到右子节点
                this.right.add(node);
            }
        }

        if (this.rightHeight() - this.leftHeight() > 1) {
            if(this.right.leftHeight() > this.right.rightHeight()){
                this.right.rightRoute();
            }
            leftRoute();
            return;
        }

        if (this.leftHeight() - this.rightHeight() > 1) {
            //当当前节点（A）的左子节点(B)的左子树的高度小于 B 节点的右子树的高度时，需要先将 B 节点进行向左旋转
            if(this.left.rightHeight() > this.left.leftHeight()){
                this.left.leftRoute();
            }
            //然后在将当前节点向右旋转
            rightRoute();
        }
    }

    /**
     * 查找节点
     *
     * @param val
     * @return
     */
    public AvlNode searchNode(int val) {
        if (this.no == val) {
            return this;
        } else if (val > this.no) {
            if (this.right == null) {
                return null;
            }
            return this.right.searchNode(val);
        } else {
            if (this.left == null) {
                return null;
            }
            return this.left.searchNode(val);
        }
    }


    /**
     * 寻找节点的父节点
     *
     * @param val
     * @return
     */
    public AvlNode searchParentNode(int val) {
        if (this.left != null && this.left.no == val) {
            return this;
        }
        if (this.right != null && this.right.no == val) {
            return this;
        }
        if (this.left != null && val < this.no) {
            return this.left.searchParentNode(val);
        } else if (this.right != null && val >= this.no) {
            return this.right.searchParentNode(val);
        }
        return null;
    }

    /**
     * 获取最小的节点
     *
     * @return
     */
    public AvlNode getMinNode() {
        if (this.left == null) {
            return this;
        } else {
            return this.left.getMinNode();
        }
    }


    /**
     * 中序遍历
     */
    public void midOrder() {
        if (this.left != null) {
            this.left.midOrder();
        }
        System.out.print(this + "  ");
        if (this.right != null) {
            this.right.midOrder();
        }
    }

    @Override
    public String toString() {
        return "AvlNode{" +
                "no=" + no +
                '}';
    }

}


